#include<iostream>
#include<map>
#include<stack>
#include<vector>
#include<string>
#include <set>
using namespace std;

class Solution {
public:

    int midtoend(string& s, int pos, vector<string>& evalRPN, map<char, int>& s_symbol)
    {
        stack<char> symbol;
        for(int i = pos;i<s.size();i++)
        {
            if (s[i] == ' ')
                continue;
            if (s[i] == '(')
            {
                i = midtoend(s, i + 1, evalRPN, s_symbol);
            }
            else if (s[i] == ')')
            {
                while (!symbol.empty())
                {
                    string ss;
                    ss += symbol.top();
                    symbol.pop();
                    evalRPN.push_back(ss);
                }
                return i;
            }
            else if (s[i] != '+' && s[i] != '-' && s[i] != '*' && s[i] != '/')
            {
                int j = s.find_first_of("()+-*/", i);
                evalRPN.push_back(s.substr(i, j - i));
                int k = 0;
                while (k<evalRPN[evalRPN.size() - 1].size())
                {
                    if (evalRPN[evalRPN.size() - 1][k] == ' ')
                        evalRPN[evalRPN.size() - 1].erase(k);
                    else 
                        k++;
                }
                if(j==string::npos)
                {
                    break;
                }
            }
            else 
            {
                if (symbol.empty() || s_symbol[(symbol.top())] < s_symbol[s[i]])
                {
                    symbol.push(s[i]);
                }
                else
                {
                    string ss;
                    ss += symbol.top();
                    evalRPN.push_back(ss);
                    symbol.pop();
                    symbol.push(s[i]);
                }
            }
        }
        while (!symbol.empty())
        {
            string ss;
            ss += symbol.top();
            symbol.pop();
            evalRPN.push_back(ss);
        }
        return 0;
    }

    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (int i = 0; i < tokens.size(); i++)
        {
            int count = 0;
            for (int j = tokens[i].size() - 1; j >= 0; j--)
            {
                if ((tokens[i][j] >= '0' && tokens[i][j] <= '9') || (tokens[i].size() > 1 && tokens[i][j] == 45))
                {
                    if ((tokens[i][j] >= '0' && tokens[i][j] <= '9'))
                    {
                        int n = tokens[i][j] - '0';
                        count += n * pow(10, (tokens[i].size() - j - 1));
                    }
                    else
                    {
                        count = -count;
                    }
                }
                else
                {
                    int a = st.top();
                    st.pop();
                    int b = st.top();
                    st.pop();
                    if (tokens[i][j] == 42)
                        count = a * b;
                    else if (tokens[i][j] == 43)
                        count = a + b;
                    else if (tokens[i][j] == 45)
                        count = b - a;
                    else if (tokens[i][j] == 47)
                        count = b / a;
                }
            }
            st.push(count);
        }
        return st.top();
    }

    int calculate(string& s) {
        map<char, int> s_symbol;
        stack<char> symbol;
        vector<string> evalRPN_;
        s_symbol.insert(make_pair('+', 1));
        s_symbol.insert(make_pair('-', 1));
        s_symbol.insert(make_pair('*', 2));
        s_symbol.insert(make_pair('/', 2));
        midtoend(s, 0, evalRPN_, s_symbol);
        cout<<evalRPN(evalRPN_);
        return 0;
    }
};
int main()
{

	//string s("\\/*+-");
	//int i = s.find('\\');
	//map<char, int> s_symbol;
    string s = "1-(     -2)";
    Solution ss;
    ss.calculate(s);
	//cout << i;
}